package leetcode_200;

import helpclass.ListNode;

/**
 *@author 周杨
 *LinkedListCycleII_142 类似141问题 找出环的开始节点
 *describe:问题1 为什么快指针一点会遇到慢指针？ 因为快指针可以看做在慢指针的后面 它在逐渐接近慢指针 终究会遇到
 *		       问题2 为什么相遇点就是环的开始点 因为一开始让快指针两倍速度 此时相当于x走的距离就是一个环的距离 因为y是它的两倍 
 *现在让x重新退到head而y不退 相当于y落在了环起点的x处 而离x也是一倍的距离
 *AC 100% 
 *2018年6月4日 下午3:57:25
 */
public class LinkedListCycleII_142_ {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	public ListNode detectCycle(ListNode head) {
		ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                break;
            }
        }

        if (fast == null || fast.next == null) {
            return null;
        }

        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

}
